/**
 * 最小编辑距离
 * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * @param word1
 * @param word2
 */
const minDistance = (word1: string, word2: string): number => {
  const w1L = word1.length;
  const w2L = word2.length;

  // 如果有一个为空, 那么进行的是删除或者插入操作, 操作数刚好为长度
  if (w1L === 0 || w2L === 0) return w1L + w2L;

  const dp: number[] = new Array(w2L + 1);

  // 初始化dp
  for (let i = 0; i <= w2L; i++) {
    dp[i] = i; // w1为空, w2不为空, 为w1转为w2只需要插入i个字符
  }

  for (let i = 1; i <= w1L; i++) {
    //   先保存左下角
    let cur = dp[0]
    dp[0] = i

    for (let j = 1; j <= w2L; j++) {
      let tmp = cur; // 左下角的值

      cur = dp[j];

      // 左边
      const left = dp[j - 1] + 1;
      //   下边
      const down = dp[j] + 1;

      // 左下角
      let leftDown = tmp;

      if (word1[i - 1] !== word2[j - 1]) {
        //   左下角加一, 如果相等的话, 左下角不用加
        leftDown++;
      }

      dp[j] = Math.min(left, down, leftDown);
    }
  }

  return dp[w2L];
};

const minDistance2 = (word1: string, word2: string): number => {
  const w1L = word1.length;
  const w2L = word2.length;

  // 如果有一个为空, 那么进行的是删除或者插入操作, 操作数刚好为长度
  if (w1L === 0 || w2L === 0) return w1L + w2L;

  // dp[i][j] 字符串word1的前i个字符转为字符串word2的前j个字符的最小编辑距离
  const dp: number[][] = [];

  // 初始化dp[i][0]
  let i = 0;
  for (; i < w1L + 1; i++) {
    dp[i][0] = i; // w2为空, w1不为空, w1 -> w2要删除, 操作数就是i
  }

  // 初始化dp[0][i]
  for (i = 0; i < w2L + 1; i++) {
    dp[0][i] = i; // w1为空, w2不为空, 为w1转为w2只需要插入i个字符
  }

  for (let i = 1; i <= w1L; i++) {
    for (let j = 1; j <= w2L; j++) {
      // 左边
      const left = dp[i - 1][j] + 1;
      //   下边
      const down = dp[i][j - 1] + 1;

      // 左下角
      let leftDown = dp[i - 1][j - 1];

      if (word1[i - 1] !== word2[j - 1]) {
        //   左下角加一, 如果相等的话, 左下角不用加
        leftDown++;
      }
      dp[i][j] = Math.min(left, down, leftDown);
    }
  }

  return dp[w1L][w2L];
};

console.log(minDistance("intention", "execution"))
console.log(minDistance("horse", "ros"))

